package simple;

/**
 求给定二叉树的最大深度，
 深度是指树的根节点到任一叶子节点路径上节点的数量。
 最大深度是所有叶子节点的深度的最大值。
 （注：叶子节点是指没有子节点的节点。）


 数据范围：0 \le n \le 1000000≤n≤100000，树上每个节点的val满足 |val| \le 100∣val∣≤100
 要求： 空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)
 示例1
 输入：
 {1,2}
 返回值：
 2
 * @author WangZhiJian
 * @since 2022/1/14
 */
public class 二叉树的最大深度 {

    public int maxDepth (TreeNode root) {
        // write code here
        return nextDepth(root,0);
    }
    public int nextDepth(TreeNode root,int curDepth){
        if(root == null)
            return curDepth;
        return Math.max(nextDepth(root.left,curDepth+1),nextDepth(root.right,curDepth+1));
    }

    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
}
